#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    string longestWord(vector<string>& words)
    {
        std::unordered_set<std::string> cnt;
        std::unordered_set<std::string> prev;

        std::sort(words.begin(), words.end());

        for (const std::string& word : words)
        {
            std::string sub;
            size_t n = word.size();
            size_t i = 0;

            for (; i < n - 1; ++i)
            {
                sub += word[i];
                if (prev.count(sub) == 0) {
                    break;
                    cnt.erase(sub);
                }
            }

            // printf("i:%d, size:%u\n", i, cnt.size());
            sub.clear();
            if (i == n - 1)
            {
                for (char ch : word)
                {
                    sub += ch;
                    cnt.erase(sub);
                }
                cnt.insert(word);
            }

            prev.insert(word);
        }

        if (cnt.empty())
        {
            return std::string();
        }

        std::string ret = *(cnt.begin());
        auto iter = ++cnt.begin();

        // std::cout << ret << std::endl;

        while (iter != cnt.end())
        {
            if ((*iter).size() > ret.size() || ((*iter).size() == ret.size() && *iter < ret)) ret = *iter;
            ++iter;
        }

        return ret;
    }
};